In der letzten Vorlesung haben wir uns über informierte Suchstrategien unterhalten und

sind bei der A-Sternsuche und bei Heuristiken herausgekommen. Heute wollen wir uns lokale

Suchstrategien angucken. Das ist eine Variante, die sich für einen anderen Satz von Problemen

eignet und dann hinterher in Richtung Spielesuche, Minimax, Alphabetaproening und so etwas bewegen.

Dabei haben wir uns gedacht, dass wir einen Teil der Hausaufgaben als ein Projekt machen werden,

wo wir sie gegeneinander bei einem bestimmten Spiel, also einen Spielalgorithmus implementieren

lassen und gegeneinander antreten lassen. Dazu komme ich aber erst nach der Wiederholung,

dann würde ich das gerne mit Ihnen besprechen. Informierte Suche ist, wenn man zusätzliche

Informationen hat, zu der die direkt in der Problemformulierung gegeben ist. Typischerweise

gibt es eine Problemformulierung, im Wesentlichen so etwas wie einen Möglichkeitenraum. Den

Möglichkeitenraum aller möglichen Pläne zu einer Lösung und das ist im Prinzip genug,

wenn man genug Zeit hat. Idealerweise hat man noch mehr Informationen und diese Situation

mit einer Karte ist prototypisch dafür. Eine Karte gibt einem mehr Informationen als man

normalerweise hat. Es gibt einem nämlich eine Abstandsintuition und dadurch eine Heuristik,

also eine Funktion, die einem sagt, wie gut ist das, was ich gerade mache? Läufe ich in

die richtige Richtung? Und das ist genau das, was wir untersucht haben. Wir haben informierte

Suche uns angeguckt, wir haben zwei Varianten angeguckt, einmal Gritty Search, das hat nicht

so gut geklappt und dann einmal A-Sternsuche und das hat gut geklappt. Wir haben sogar

einen Optimalitätssatz dafür bewiesen am Ende. Wichtig ist, wir haben zusätzliche

Informationen und die zusätzliche Information ist in diesem Framework gegeben durch eine

sogenannte Heuristik und Heuristik ist einfach eine Bewertungsfunktion dessen, wie gut ist

das, was wir gerade erreicht haben? Beziehungsweise für alle die Kindknoten, die wir jetzt als

nächstes explorieren können, welcher sieht am besten aus? In einem Schritt. Wir haben

uns als Beispiel immer hier die Fahrtplanung in Rumänien angeguckt und haben gesehen,

dass die Heuristik der Luftlinie immer ganz gut funktioniert, außer in Situationen, wo

man Situationen hat, wo man in die Irre laufen kann, hier in diesem Irrgartenartigen Fahrtplanungsproblem,

wo wir da einen langen, langen, langen Irrweg haben und in den man mit einfacher besten

Suche auch tatsächlich immer reinläuft. Wir haben uns Heuristiken genauer angeguckt,

wir haben auch Zieldistance genannt und das gibt einem genau die Intuition dazu, wir

abhoximieren, wie weit es noch bis zum Ziel ist und je kürzer es zum Ziel ist, so besser,

hoffentlich. Und wir haben uns bei Eigenschaften von Heuristiken angeguckt, die Zulässigkeit

und die Konsistenz, Zulässigkeit als eine globale Eigenschaft, in der man die Heuristik

vergleicht mit der idealen Heuristik, mit dem tatsächlichen Zielabstand und wir haben

eine, das ist wichtig, wir haben eine Heuristik zulässig genannt, wenn sie unterschätzt.

Und hinterher in der A-Stern-Suche war es ja dann so, dass wenn wir Zulässigkeit haben,

dass wir dann auch Optimalität garantieren können. Zulässigkeit ist aber eine Sache,

die kann man nur dann nachweisen, wenn man schon weiß, was die ideale Heuristik ist.

Also das ist eine rein theoretische Bedingung. Wenn man nämlich weiß, was H-Stern ist,

dann braucht man den ganzen Cladraraatsch nicht mehr machen, dann kann man einfach sich

von H-Stern leiten lassen. Deswegen haben wir noch eine weitere Bedingung eingeführt,

nämlich Konsistenz und Konsistenz ist eine lokale Bedingung, die kann man einfach nachprüfen.

Da müssen wir jeden Zustand laufen und gucken, ob die, ob die Operator, ob jede Operatoranwendung

tatsächlich ihre echten Kosten unterschätzt. Und wir haben bewiesen, dass Konsistenz tatsächlich

Zulässigkeit impliziert und dass wir dadurch dann hinterher in der A-Stern-Suche auch Optimalität

bekommen. Das sind so die bestaler Welten in gewisser Weise. A-Stern-Suche, wie funktioniert

das? A-Stern-Suche ist nichts anderes als besten Suche nur mit einem zusätzlichen Frustrationsterm

und der Frustrationsterm sind einfach die Pfadkosten bisher. Egal was wir machen, die

Kosten werden immer aufmordiert und wenn wir wie ein Hühnchen hin und her und hin und her

laufen, dann wächst die Frustration und wird natürlich in die ganze Sache mit eingebaut

und dadurch kriegen wir dann die Optimalität. Wir haben uns dann ein Beispiel angeguckt,